~~看一下这道题的题面,决定放弃这道题,~~突然想起在 上可能会有英文翻译,便到原题看了一眼,真的有。题意大概是:
- 输入一个仅由 和 组成的字符串 ,假设共 位;
- 请你构造一个共 位数列 ,满足 最小,同时 与 的关系是 中的字符(即:大于或小于)。
- 输出
看了一眼数据规模,想到一个 的暴力解法:
- 从前往后扫一遍字符串,构造 对应的值,具体方法: ,可以证明这是最优方案;
- 从后往前扫一遍字符串,构造 对应的值,具体方法: ,可以证明这是最优方案。
最后再扫一遍记好的数组,记录 ,输出即可,注意 可能需要使用 。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
ll l, a[500001];
ll ans;
int main()
{
cin>>s;
s = " " + s;
l = s.length() - 1;
for(int i=1;i<=l;i++) (s[i] == '<') ? (a[i+1] = a[i] + 1) : (a[i+1]);
for(int i=l;i>=1;i--) (s[i] == '>') ? (a[i] = max(a[i], a[i+1]+1)) : (a[i]);
for(int i=1;i<=l+1;i++) ans += a[i];
cout<<ans<<endl;
return 0;
}